package com.yubest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
 *
 * 0 <= a, b, c, d < n
 * a、b、c 和 d 互不相同
 * nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [1,0,-1,0,-2,2], target = 0
 * 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
 * 示例 2：
 *
 * 输入：nums = [2,2,2,2,2], target = 8
 * 输出：[[2,2,2,2]]
 *  
 *
 * 提示：
 *
 * 1 <= nums.length <= 200
 * -10^9 <= nums[i] <= 10^9
 * -10^9 <= target <= 10^9
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/4sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/1 10:41
 */
public class P0018 {

    public static void main(String[] args) {
        System.out.println(new Solution18().fourSum(new int[]{1,0,-1,0, -2, 2}, 0));

        System.out.println(new Solution18().fourSum(new int[]{2, 2, 2, 2, 2}, 8));
    }
}

class Solution18 {

    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums.length < 4) {
            return new ArrayList<>(0);
        }
        Arrays.sort(nums);
        int len = nums.length;

        List<List<Integer>> result = new ArrayList<>();

        for (int first = 0; first < len; first++) {
            //过滤重复的计算
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            for (int second = first + 1; second < nums.length; second++) {
                if (((long) nums[first] + (long) nums[second]) >= Integer.MAX_VALUE
                        || ((long) nums[first] + (long) nums[second]) <= Integer.MIN_VALUE) {
                    break;
                }
                //过滤重复的计算
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                for (int third = second + 1; third < nums.length; third++) {
                    if (((long) nums[first] + (long) nums[second] + (long) nums[third]) >= Integer.MAX_VALUE
                            || ((long) nums[first] + (long) nums[second] + (long) nums[third]) <= Integer.MIN_VALUE) {
                        break;
                    }
                    //过滤重复的计算
                    if (third > second + 1 && nums[third] == nums[third - 1]) {
                        continue;
                    }
                    for (int four = third + 1; four < nums.length; four++) {
                        if (((long) nums[first] + (long) nums[second] + (long) nums[third] + (long) nums[four]) >= Integer.MAX_VALUE
                                || ((long) nums[first] + (long) nums[second] + (long) nums[third] + (long) nums[four]) <= Integer.MIN_VALUE) {
                            break;
                        }
                        //过滤重复的计算
                        if (four > third + 1 && nums[four] == nums[four - 1]) {
                            continue;
                        }
                        if (target == nums[first] + nums[second] + nums[third] + nums[four]) {
                            List<Integer> t = new ArrayList<>();
                            t.add(nums[first]);
                            t.add(nums[second]);
                            t.add(nums[third]);
                            t.add(nums[four]);
                            result.add(t);
                            break;
                        }
                    }
                }
            }
        }
        return result;
    }
}
